#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int N = 2e4+10;

int tot,h[N],nodenum,rt[N],ls[N<<8],rs[N<<8],s[N<<8],n,m,b[N],ans;

void update(int &y,int pos,int v,int l = 0,int r = tot+1){
	if(!y) y = ++nodenum;
	s[y] += v;
	if(l == r) return;
	int mid = l+r>>1; if(pos <= mid) update(ls[y],pos,v,l,mid);else update(rs[y],pos,v,mid+1,r);
}

int query(int y,int xl,int xr,int l = 0,int r = tot+1){
	if(!y) return 0; if(xl == l && xr == r) return s[y];
	int mid = l + r>>1;
	if(xr <= mid) return  query(ls[y],xl,xr,l,mid);
	else if(xl > mid) return query(rs[y],xl,xr,mid+1,r);
	else return query(ls[y],xl,mid,l,mid) + query(rs[y],mid+1,xr,mid+1,r);
}

int query_pre(int pos,int xl,int xr){int res = 0; for(int i = pos;i;i-=i&-i) res = res + query(rt[i],xl,xr); return res;}

void update_pre(int pos,int num,int v){for(int i = pos;i <= n;i+=i&-i) update(rt[i],num,v);}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in; for(int i = 1;i <= n;i++) h[i] = in,b[++tot] = h[i]; m = in;
	sort(b+1,b+tot+1); tot = unique(b+1,b+tot+1) - b - 1;
	for(int i = 1;i <= n;i++){
		h[i] = lower_bound(b+1,b+tot+1,h[i]) - b;
		ans += query_pre(i-1,h[i] + 1,tot+1);
		update_pre(i,h[i],1);
	}
	printf("%d\n",ans);
	for(int i = 1;i <= m;i++){
		int x = in,y = in; if(x == y) {printf("%d\n",ans);continue;}
		ans -= query_pre(y-1,0,h[x]-1) - query_pre(x,0,h[x]-1);
		ans += query_pre(y-1,h[x]+1,tot+1) - query_pre(x,h[x]+1,tot+1);
		ans += query_pre(y-1,0,h[y]-1) - query_pre(x,0,h[y]-1);
		ans -= query_pre(y-1,h[y]+1,tot+1) - query_pre(x,h[y]+1,tot+1);
		if(h[x] < h[y]) ans++; if(h[x] > h[y]) ans--;
		update_pre(x,h[x],-1); update_pre(y,h[y],-1);
		swap(h[x],h[y]); update_pre(x,h[x],1); update(y,h[y],1);
		printf("%d\n",ans);
	}
	return 0;
}

